package cn.itsource.list.linkedlist;

import java.util.LinkedList;

/**
 * 集合框架：
	Iterable（迭代器接口，实现了该接口可以使用foreach,还可以获取集合对象的迭代器对象，通过迭代器遍历集合） 
		|
		|---iterator() =======>Iterator
		|					  		|	
		|	listIterator()获取	ListIterator
		|
 * 	Collection(所有集合的根接口)  
 * 		|----List(接口)表示有序（存入和取出）可重复集合，可以保存null元素 
 * 				|---ArrayList(实现类) 基于数组，查改快  
 * 				|---LinkedList(实现类)基于变量，增删快 
 * 				|	因为LinkedList中有多个接口的实现方法，所以，同样一个功能可以有多个方法实现，
 * 					但是，尽量不要交叉使用（使用同一个接口中的方法），因为交叉使用就会导致
 *					既不能完全具其中有一个接口的完整特性
 * 				|---Vector(就是一个线程安全的ArrayList) 
 * 
 * 		|----Set(接口)表示无序（存入和取出）不可重复集合，可以保存null元素
 * 				|----HashSet(实现类)：基于HashMap，HashMap基于HashCode，是一个非线程安全。
 * 						判断重复的机制：
 * 							1. 先判断元素的hashCode值
 * 							2. 在hashCode相等的情况下，继续判断equals比较，如果都相等认为是同一个元素
 * 
 * 				|----TreeSet(实现类)：基于TreeMap，TreeMap底层基于红黑树（特殊的二叉树，左边叉值小，右边叉值大）
 * 				|		1. 自然排序：元素类型必须实现了Comparable接口，且必须重写compareTo（）方法
							返回值  正数：升序
						           返回值 负数：降序
							返回值0：相同的元素
							
						2. 定制排序：
 * 							在创建TreeSet对象的时候，传入一个Comparator接口的实现类，该实现类必须重写compare方法
 * 							返回值  正数：升序
						           返回值  负数：降序
							返回值 0：相同的元素
 * 					当自然排序和定制排序同时使用，定制排序优先级更高
 * 				|
 * 				|----LinkedHashSet(是一个有序的HashSet，在HashSet基础上维护了一个链表) 
 * 
 * 		|-----Queue队列 
 * 				|---Deque双端队列
 * 			 	|---Stack栈
 * 
 * 
 * 	集合遍历方式：		只有List才有双向迭代器
 * 
 *		1. foreach()因为ArrayList间接实现了Iterable接口
 *		2. 迭代器：一个集合对象可以获取多个迭代器对象（多次调用方法）,指针都是在初始位置（第一个元素前面）
 *			Iterator<E> iterator()  单向迭代器
 *				1. boolean hasNext() 如果迭代具有更多元素，则返回 true 。  
				2. Object next() 返回迭代中的下一个元素。  
				3. default void remove() 从底层集合中删除此迭代器返回的最后一个元素（可选操作）。 
			
			ListIterator<E> listIterator() 双向迭代器
				void add(E e) 
					将指定的元素插入列表（可选操作）。  
				boolean hasNext() 
					返回 true如果遍历正向列表，列表迭代器有多个元素。  
				boolean hasPrevious() 
					返回 true如果遍历反向列表，列表迭代器有多个元素。  
				E next() 
					返回列表中的下一个元素，并且前进光标位置。  
				int nextIndex() 
					返回随后调用 next()返回的元素的索引。  
				E previous() 
					返回列表中的上一个元素，并向后移动光标位置。  
				int previousIndex() 
					返回由后续调用 previous()返回的元素的索引。  
				void remove() 
					从列表中删除由 next()或 previous()返回的最后一个元素（可选操作）。  
				void set(E e) 
					用 指定的元素替换由 next()或 previous()返回的最后一个元素（可选操作）。  

 *		3.遍历集合方式3：通过普通for循环，利用集合size()方法和get(int index)	（不常用）
 *
 * 		注意：在使用迭代器遍历集合的时候，不能使用集合自己的方法（增删改）操作集合对象
 */
public class LinkedListTest {

	public static void main(String[] args) {
		/*
		 * 构造方法
		 * 		LinkedList() 构造一个空列表。  
				LinkedList(Collection c) 构造一个包含指定集合的元素的列表，按照它们由集合的迭代器返回的顺序。  
		 */
		LinkedList list = new LinkedList();
		
		//常用方法：
		//void push(E e) 元素入栈（栈的特点）  
		list.push("A");
		list.push("B");
		list.push("C");
		list.push("D");
		list.push("E");
		list.push("F");
		list.push("G");
		list.push("H");
		System.out.println(list);
		
//		//区别add方法
//		LinkedList list2 = new LinkedList();
//		list2.add("A");
//		list2.add("B");
//		list2.add("C");
//		list2.add("D");
//		list2.add("E");
//		list2.add("F");
//		list2.add("G");
//		list2.add("H");
//		System.out.println(list2);
		
		//E pop() 删除并且返回最后添加的元素（栈的特点）  
//		Object pop = list.pop();
//		System.out.println(pop);
//		System.out.println(list);
		
		//练习题
		for (int i = 0; i < list.size(); i++) {//[H, G, F, E, D, C, B, A]
			System.out.println(list.pop());//H, G, F, E		摔倒的地方
		}
		
		
		//以下方法自己练习
		//boolean add(E e) 将指定的元素追加到此列表的末尾。  
		//void add(int index, E element) 在此列表中的指定位置插入指定的元素。  
		//boolean addAll(Collection<? extends E> c) 按照指定集合的迭代器返回的顺序将指定集合中的所有元素追加到此列表的末尾。  
		//boolean addAll(int index, Collection<? extends E> c) 将指定集合中的所有元素插入到此列表中，从指定的位置开始。  
		//void addFirst(E e) 在该列表开头插入指定的元素。  
		//void addLast(E e) 将指定的元素追加到此列表的末尾。  
		//void clear() 从列表中删除所有元素。  
		//boolean contains(Object o) 如果此列表包含指定的元素，则返回 true 。  
		
		//E element() 检索但不删除此列表的头（第一个元素）。  
		//E get(int index) 返回此列表中指定位置的元素。  
		//E getFirst() 返回此列表中的第一个元素。  
		//E getLast() 返回此列表中的最后一个元素。  
		//int indexOf(Object o) 返回此列表中指定元素的第一次出现的索引，如果此列表不包含元素，则返回-1。  
		//int lastIndexOf(Object o) 返回此列表中指定元素的最后一次出现的索引，如果此列表不包含元素，则返回-1。  
		//ListIterator<E> listIterator(int index) 从列表中的指定位置开始，返回此列表中元素的列表迭代器（按适当的顺序）。  
		//boolean offer(E e) 将指定的元素添加为此列表的尾部（最后一个元素）。  
		//boolean offerFirst(E e) 在此列表的前面插入指定的元素。  
		//boolean offerLast(E e) 在该列表的末尾插入指定的元素。  
		//E peek() 检索但不删除此列表的头（第一个元素）。  
		//E peekFirst() 检索但不删除此列表的第一个元素，如果此列表为空，则返回 null 。  
		//E peekLast() 检索但不删除此列表的最后一个元素，如果此列表为空，则返回 null 。  
		//E poll() 检索并删除此列表的头（第一个元素）。  
		//E pollFirst()检索并删除此列表的第一个元素，如果此列表为空，则返回 null 。  
		//E pollLast()检索并删除此列表的最后一个元素，如果此列表为空，则返回 null 。  
		//E remove() 检索并删除此列表的头（第一个元素）。  
		//E remove(int index) 删除该列表中指定位置的元素。  
		//boolean remove(Object o) 从列表中删除指定元素的第一个出现（如果存在）。  
		//E removeFirst() 从此列表中删除并返回第一个元素。  
		//
		//E removeLast() 从此列表中删除并返回最后一个元素。  
		//
		//E set(int index, E element) 用指定的元素替换此列表中指定位置的元素。  
		//int size()  返回此列表中的元素数。
		//
		//Object[] toArray()  将集合对象转换为数组
	}

}
